package pers.qianyu.month_202011.date_20201118;

import java.util.*;

/**
 * 1288. 删除被覆盖区间
 * https://leetcode-cn.com/problems/remove-covered-intervals/
 *
 * @author mizzle rain
 * @date 2020-11-18 10:46
 */
public class RemoveCoveredIntervals {
    public int removeCoveredIntervals(int[][] intervals) {
        if (intervals.length == 1) {
            return 1;
        }
        int res = intervals.length;
        /**
         * 先按照区间左端点升序排列
         * 如果左端点相同，就按照右短点降序排列
         */
        Arrays.sort(intervals, (item1, item2) -> {
            int a = item1[0] - item2[0];
            return a == 0 ? item2[1] - item1[1] : a;
        });
        // System.out.println(Arrays.deepToString(intervals));
        for (int i = 1; i < intervals.length; i++) {
            int[] cur = intervals[i];
            int[] pre = intervals[i - 1];
            if (cur[1] <= pre[1]) {
                // 如果前一个区间包含当前区间，就把当前区间置为前一个区间
                cur[1] = pre[1];
                cur[0] = pre[0];
                res--;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] arr = {{1, 2}, {1, 4}, {3, 4}};
        int result = new RemoveCoveredIntervals().removeCoveredIntervals(arr);
        System.out.println("result = " + result);
    }
}
